Toward a Dynamic Programming Solution for the 4-peg Tower of Hanoi Problem with Configurations

摘要

The Frame-Stewart algorithm for the 4-peg variant of the Tower of Hanoi,introduced in 1941, partitions disks into intermediate towers before moving theremaining disks to their destination. Algorithms that partition the disks havenot been proven to be optimal, although they have been verified for up to 30disks. This paper presents a dynamic programming approach to this algorithm,using tabling in B-Prolog. This study uses a variation of the problem,involving configurations of disks, in order to contrast the tabling approachwith the approaches utilized by other solvers. A comparison of differentpartitioning locations for the Frame-Stewart algorithm indicates that, althoughcertain partitions are optimal for the classic problem, they need to bemodified for certain configurations, and that random configurations mightrequire an entirely new algorithm.